Recent development in the three-dimensional object shape measurement technology has made it possible to obtain highly accurate three-dimensional shape data for objects having non-geometrical, complicated free shapes (see, for example, “A Range Finder for Human Face Measurement”, IEICE Technical Report, vol. 99, No. 118, PRMU 99-223, pp. 35-42 (Non-Patent Document 1)), and three-dimensional shape data is now utilized in various fields such as a graphics generation system and an image recognition system.
A complicated three-dimensional shape of an object (a human body, for example), which cannot be described by a combination of geometrical shapes such as cubes or circular cylinders, is usually represented as a set of triangular or quadrangular facets (polygons) obtained by finely dividing the object surface, and described by data formed of a series of coordinate values of the vertexes in three-dimensional space. Color information of an object surface is represented by brightness values as colors of the polygon vertexes.
According to a typical method of representing 3D data, for example, a two-dimensional coordinate system (u, v) is defined on the surface of an object in the same manner as the latitudes and longitudes are determined on the surface of the earth, the coordinates are quantized at appropriate regular intervals so that the quantized points are regarded as polygon vertexes, and the three-dimensional coordinates and color (r, g, b brightness values) thereof are stored as data. According to this method, the three-dimensional shape of an object and the color information of the surface thereof can be perceived as an image each pixel of which has six elements (x, y, z, r, g, and b).
Since three-dimensional coordinates have a wider range than brightness values, three-dimensional data has an amount of data that is several times greater than that of a brightness image having an equal level of resolution. For example, when a surface area of 30 cm×30 cm is quantized at intervals of 1 mm, data of 90,000 (resolution 300×300) vertexes is required. Even if each of x, y and z is described by two bytes, and each of r, g and b is described by one byte, the data amount exceeds 800 kilo bytes. Accordingly, in a system using three-dimensional data of a multiplicity of objects as compared with an image processing system, a problem becomes more serious about a data amount in various data processing processes such as storage, search, and network transmission of data, and, as a result, a technology to compress the data amount is required.
An example of a conventional compression apparatus compressing three-dimensional shape data for reducing the data amount of a three-dimensional shape model represented with polygons is described in W. J. Schroeder, J. A. Zarge, W. E. Lorensen, “Decimation of Triangle Meshes”, Computer Graphics, 26,2, 1992, Pages: 65-70 (Non-Patent Document 2). As shown in FIG. 22, this conventional data compression apparatus 2000 is composed of vertex selection means 2001 and vertex deletion means 2002.
The data compression apparatus 2000 thus configured operates as described below.
The vertex selection means 2001 selects such vertexes that can be deleted without causing a serious error from input three-dimensional data 2010, and the vertex deletion means 2002 deletes the selected vertexes to reduce the number of polygons to thereby generate compressed data 2020 that is three-dimensional data with a reduced data amount. According to the technology described in Non-Patent Document 2, the vertex selection means 2001 preferentially selects vertexes located at a short distance from a polygon at an averaged position of adjacent polygons, and the vertex deletion means 2002 deletes the vertexes. This operation is repeated until reaching a designated decimation rate. The compressed data 2020 finally obtained has a reduced number of vertexes and thus has a smaller data amount in comparison with the original data. There are many similar technologies for improving the method of selecting polygon to be deleted. One of such technologies is described in Japanese Patent 3341549 (Patent Document 1).
On the other hand, although not relating to data compression, an example of techniques for generating three-dimensional shape data is described in Volker Blanz, Thomas Vetter, “A Morphable Model For The Synthesis Of 3D Faces”, SIGGRAPH 99 Conference Proceedings, Pages: 187-194 (Non-Patent Document 3). According to Non-Patent Document 3, a multiplicity of three-dimensional facial data sets are preliminarily collected, and corresponding points are determined between the data sets to produce vertex data. A principal component analysis is applied to compute about 100 sets of base data and the computed base data is stored. When a photograph of a face (two-dimensional image) is given, a three-dimensional data of the face represented by the two-dimensional image is synthesized based on a combination of the stored base data, and the three-dimensional data thus obtained is output.